package com.qjc.demo.algorithm.无重复字符的最长子串LeetCode3;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName: Solution
 * @Author: qjc
 * @Date: 2023/8/16 09:36
 */
public class Solution {
    // 无重复最长子串
    public static int notRepeatLongestSubstring(String s) {
        // 定义最长子串长度
        int max = 0;
        // 定义一个map存储字符下标，key-字符，value-字符对应下标
        Map<Character, Integer> map = new HashMap<>();
        for (int start = 0, end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            // 判断该字符是否已经存在
            if (map.containsKey(c)) {
                // 如果已经存在则更新start = 与该字符重复的上一个字符的下标+1
                start = Math.max(start, map.get(c) + 1);
            }
            // 将字符和字符下标存入map
            map.put(c, end);
            // 更新最大长度
            max = Math.max(max, end - start + 1);
        }
        return max;
    }

    public static void main(String[] args) {
        String s = "pdvdf";
        System.out.println(notRepeatLongestSubstring(s));
    }

}
